package demo1;

import java.util.Arrays;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:快速排序-归并排序-复习
 * User: 石方旭
 * Date: 2022-06-27
 * Time: 7:23
 */
public class TestDemo {

    public static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    //前后指针法
    public static int partition(int[] array,int left,int right){
         int prev = left;
         int cur = left+1;
         int pivot = left;
         while(cur<=right){
             if(array[cur]<array[pivot]&& ++prev !=cur){
                 swap(array,prev,cur);
             }
             ++cur;
         }
         //cur走到结尾 prev是基准位置
        swap(array,prev,pivot);
         return prev;
    }

    //快速排序非递归版本
    public static void quickSortNor(int[] array,int left,int right){
        Stack<Integer> stack = new Stack<>();
        int mid = partition(array,left,right);
        if(left<mid-1){
            stack.push(left);
            stack.push(mid-1);
        }
        if(right>mid+1){
            stack.push(mid+1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            mid = partition(array,left,right);
            if(left<mid-1){
                stack.push(left);
                stack.push(mid-1);
            }
            if(right>mid+1){
                stack.push(mid+1);
                stack.push(right);
            }
        }

    }

    public static void quickSort(int[] array,int left,int right){
        if(left>=right) return ;
        int mid = partition(array,left,right);
        quickSort(array,left,mid-1);
        quickSort(array,mid+1,right);
    }

    public static void Merge(int[] array,int left,int mid,int right) {
        int b1 = left;
        int e1 = mid;
        int b2 = mid+1;
        int e2 = right;
        int[] tmp = new int[right-left+1];
        int k =0;
        while(b1<=e1&&b2<=e2){
            if(array[b1]<array[b2]){
                tmp[k++] = array[b1++];
            }else {
                tmp[k++] = array[b2++];
            }
        }
        while(b1<=e1){
            tmp[k++] = array[b1++];
        }
        while(b2<=e2){
            tmp[k++] = array[b2++];
        }
        for(int i =0;i<k;++i){
            array[i+left] = tmp[i];
        }
    }

    //归并排序的非递归版本

    public static void MergeSortNor(int[] array,int left,int right){
        int gap =1;
        int mid = left+((right-left)>>>1);
        while(gap<array.length){
            for(int i = 0;i<array.length;i+=2*gap){
                left = i;
                mid = left+gap-1;
                if(mid>=array.length){
                    mid = array.length-1;
                }
                right = mid+gap;
                if(right>=array.length){
                    right = array.length-1;
                }
                Merge(array,left,mid,right);
            }
            gap*=2;
        }
    }

    public static void MergeSort(int[] array,int left,int right){
        if(left>=right) return;
        int mid = left+((right-left)>>>1);
        MergeSort(array,left,mid);
        MergeSort(array,mid+1,right);
        Merge(array,left,mid,right);
    }

    public static void main(String[] args) {
        int[] array = {27,56,32,9,63,45,82,1,73,69,85,75,98,0,};
        //归并排序
        MergeSortNor(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }

    public static void main1(String[] args) {
        int[] array = {27,56,32,9,63,45,82,1,73,69,85,75,98,0,};
        quickSortNor(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }
}
